package com.xzz.dfs;

/**
 * @author: hhz
 * @create: 2022-01-24 15:50
 * 130. 被围绕的区域
 **/
public class Solve {
    public static void main(String[] args) {
        solve(new char[][]{{'X','X','X','X'},{'X','O','O','X'},{'X','X','O','X'},{'X','O','X','X'}});
        solve(new char[][]{{'O','O','O'},{'O','O','O'},{'O','O','O'}});
    }
    public static void solve(char[][] board) {
        int n = board.length;
        int m = board[0].length;
        for (int i = 0; i < n; i++) {
            dfs(board, i, 0);
            dfs(board, i, m - 1);
        }
        for (int j = 0; j < m; j++) {
            dfs(board, 0, j);
            dfs(board, n - 1, j);
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (board[i][j] == '#') {
                    board[i][j] = 'O';
                } else if (board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }
    public static void dfs(char[][] board,int i,int j){
        if(i<0||j<0||i>board.length-1||j>board[0].length-1 ||  board[i][j] != 'O'){
            return;
        }
        board[i][j]='#';
        dfs(board,i-1,j);
        dfs(board,i+1,j);
        dfs(board,i,j-1);
        dfs(board,i,j+1);
    }
}
